Fouille dichotomique

L'idée est simple :
Au lieu de parcourir tous les éléments un par un, on divise l’intervalle de recherche en deux à chaque étape.

1. On compare la valeur au milieu du tableau.
2. Si c’est la bonne → on a terminé.
3. Si la valeur cherchée est plus petite que celle au milieu → on cherche dans la moitié gauche.
4. Si elle est plus grande → on cherche dans la moitié droite.
5. On répète jusqu'à trouver la valeur ou que l'intervalle soit vide.

Précondition

Le tableau doit être trié en ordre croissant. Pour ça qu'on a vu les tris au derniers cours.

Complexité temporelle

• Meilleur cas : O(1) (si on tombe directement sur l’élément)
• Pire cas / moyen cas : O(log n), parce qu’on divise l’espace par deux à chaque fois.

Code

int rechercheBinaire(int[] tab, int valeur) {
    int debut = 0;
    int fin = tab.length - 1;

    while (debut <= fin) {
        int milieu = (debut + fin) / 2;

        if (tab[milieu] == valeur) {
            return milieu; 
        } else if (tab[milieu] < valeur) {
            debut = milieu + 1;
        } else {
            fin = milieu - 1;
        }
    }

    return -1; // pas trouvé
}

Exemple concret

Soit le tableau trié : [2, 4, 7, 10, 13, 15, 19]
Tu cherches 13.

Étape 1 :

• debut = 0
• fin = 6
• milieu = (0 + 6) / 2 = 3 → tab[3] = 10 Trop petit, on cherche à droite.

Étape 2 : On met debut = 4 (juste après le 10)

• debut = 4, fin = 6
• milieu = (4 + 6) / 2 = 5 → tab[5] = 15

Étape 3 :

• 15 est trop grand, donc on va chercher à gauche de 15.
• On met fin = 4
• Nouveau milieu = (4 + 4) / 2 = 4 → tab[4] = 13 → trouvé !

---

Conclusion :

1. Milieu = 10 → trop petit → cherche à droite
2. Milieu = 15 → trop grand → cherche à gauche
3. Milieu = 13 → trouvé

À surveiller

• Le calcul de milieu = (debut + fin) / 2 peut provoquer un dépassement d'entier si les indices sont très grands. On recommande parfois :

int milieu = debut + (fin - debut) / 2;